package com.company.LinkList;

import org.omg.CORBA.NO_IMPLEMENT;
import org.w3c.dom.NodeList;

import java.util.List;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}15:05
 */
public class mergeTwoList {
    public static void main(String[] args) {
        NodeList nodeList = new NodeList();
        nodeList.add(1);
        nodeList.add(2);
        nodeList.add(10);
//        System.out.println(nodeList.head);
        NodeList nodeList2 = new NodeList();
        nodeList2.add(4);
        nodeList2.add(5);
        nodeList2.add(6);
//        System.out.println(nodeList2.head);
        NodeList nodeList3 = new NodeList();
        Node node = nodeList3.mergeTwoList(nodeList.head,nodeList2.head);
        while (true) {
            System.out.println(node);
            node = node.next;
            if (node == null){
                break;
            }
        }
    }

    static class Node{
        private int no;
        private Node next;

        public int getNo() {
            return no;
        }

        public void setNo(int no) {
            this.no = no;
        }

        public Node(int no) {
            this.no = no;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "no=" + no +
                    '}';
        }
    }

    static class NodeList{
        public Node head = null;
        public void add(int no){
            Node curNode = null;
            if (head == null){
                head = new Node(no);
            }else {
                curNode = head;
                while (true){
                    if (curNode.next == null){
                        break;
                    }
                    curNode = curNode.next;
                }
                curNode.next = new Node(no);
            }
        }

//        public  Node mergeTwoList(Node node1,Node node2){
//            if (node1.next==null){
//                return node2;
//            }
//            if (node2.next==null) {
//                return node1;
//            }
//            Node head = null;
//            if (node1.no <= node2.no){
//                head = node1;
//                head.next = mergeTwoList(node1.next,node2);
//            }else {
//                head = node2;
//                head.next = mergeTwoList(node1,node2.next);
//            }
//            return head;
//        }

        public Node mergeTwoList(Node l1, Node l2) {
//            // 两条链表都为null 直接返回null
//            if(l1==null&&l2==null)
//                return null;
//            if(l1==null) // l1为null 直接返回l2
//                return l2;
//            if(l2==null) // l2 为null， 直接返回l1
//                return l1;
//            // cur 保存当前尾节点 temp 保存即将接上的节点  head 为头结点
//            Node cur=null,temp=null,head=null;
//            while(l1!=null&&l2!=null)
//            {
//                if(l1.no>=l2.no)
//                {
//                    temp = l2;
//                    l2 = l2.next;
//                }
//                else
//                {
//                    temp = l1;
//                    l1 = l1.next;
//                }
//                if(head==null)
//                    cur = head = temp;
//                else
//                {
//                    cur.next = temp;
//                    cur = temp;
//                }
//            }
//            if(l1==null)
//                cur.next = l2;
//            else
//                cur.next = l1;
//            return head;
//        }
            if (l1 == null){
                return l2;
            }
            if (l2 == null){
                return l1;
            }
            if (l1.no>l2.no){
                l2.next = mergeTwoList(l1,l2.next);
                return l2;
            }{
                l1.next = mergeTwoList(l1.next,l2);
                return l1;
            }
        }
    }
}
